package 代码随想2._6栈与队列;

/**
 * @author XXX
 * @date 2024-01-17 18:55
 */

import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * https://leetcode.cn/problems/sliding-window-maximum/description/
 */
public class _6滑动窗口最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (k>0 && k<=nums.length){
            ArrayDeque<Integer> dq = new ArrayDeque<>();
            for (int i=0;i<k;i++){
                while (!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            for (int i=k;i<nums.length;i++){
                res.add(nums[dq.peekFirst()]);
                while (!dq.isEmpty() && dq.peekFirst()<(i-k+1))
                    dq.pollFirst();
                while (!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            res.add(nums[dq.pollFirst()]);
        }
        if (res.isEmpty())
            return new int[0];
        return res.stream().mapToInt(x->x).toArray();
    }
}
